Cracking The Coding Interview 4.1

//Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

//

//	译文：

//

//	实现一个函数检查一棵树是否平衡。对于这个问题而言， 平衡指的是这棵树任意两个叶子结点到根结点的距离之差不大于1。

#include <iostream>

#include <string>

using namespace std;

class tree

{

public:

	tree()

	{

		//root = create();

		root = NULL;

		index = 0;

	}

	/***输入扩展层次遍历序列，#表示该节点为空***/

	tree(char *s)

	{

		root = NULL;

		index = 0;

		if (s == NULL)

		{

			return;

		}

		int size = strlen(s);

		create(&root,s,0,size);

	}

	~tree()

	{

		/***清空二叉树***/

	}

	/***二叉排序树：插入。***/

	void insert(char *s)

	{

		if (s == NULL)

		{

			return;

		}

		int size = strlen(s);

		for (int i = 0; i<size; i++)

		{

			insert(&root, s[i]);

		}

	}

	bool isBanlance(int size)

	{

		int *s = new int[size];

		depth(root,s,size,0);

		s[index+1] = '\0';

		int i = 0;

		int max = s[0];

		int min = s[0];

		while(s[i]!='\0')

		{

			if (s[i]>max)

			{

				max = s[i];

			}

			if (s[i]<min)

			{

				min = s[i];

			}

			i++;

		}

		return ((max - min)>1? 0:1);

	}

	void preOrder(){	pOrder(root);}

	void inOreder(){	zOrder(root);}

	void postOreder(){  hOrder(root);}

private:

	struct treenode

	{

		char data;

		treenode * left;

		treenode * right;

	};

	treenode *root;

	int index;

	void insert(treenode **p, char s)

	{

		if (((*p) == NULL) && s != '\0')

		{

			*p = new treenode;

			(*p)->data = s;

			(*p)->left = NULL;

			(*p)->right = NULL;

		}

		else

		{

			if ((*p)->data > s)

			{

				insert(&((*p)->left) , s);

			}

			else

			{

				insert(&((*p)->right) , s);

			}

		}

	}

	void depth(treenode *s, int *str,int size,int k)

	{

		if (s==NULL)

		{

			return;

		}

		if (s->left == NULL && s->right == NULL)

		{

			str[index]= k;

			index++;

		}

		else

		{

			depth(s->left,str, size, k+1);

			depth(s->right,str, size, k+1);

		}

	}

	treenode* create()

	{

		treenode *p;

		char t;

		cout<<"请输入："<<endl;

		t = getchar();

		if (t=='#')

		{

			p = NULL;

		}

		else

		{

			p = new treenode;

			p->data = t;

			cout<<"create tree node:  "<<t<<endl;

			p->left = create();

			p->right = create();

		}

		return p;

	}

	void create(treenode **p, char *str, int i, int size)

	{

		if (i>size-1 || str[i] == '\0')

		{

			*p = NULL;

			return;

		}

		if (str[i] == '#')

		{

			*p=NULL;

		}

		else

		{

			*p = new treenode;

			(*p)->data = str[i];

			create(&((*p)->left),str,2*i+1,size);

			create(&((*p)->right),str,2*i+2,size);

		}

	}

	void pOrder(treenode *p)

	{

		if (p==NULL)

		{

			return;

		}

		cout<<p->data<<"  "<<endl;

		pOrder(p->left);

		pOrder(p->right);

	}

	void zOrder(treenode *p)

	{

		if (p==NULL)

		{

			return;

		}

		zOrder(p->left);

		cout<<p->data<<"  "<<endl;

		zOrder(p->right);

	}

	void hOrder(treenode *p)

	{

		if (p==NULL)

		{

			return;

		}

		hOrder(p->left);

		cout<<p->data<<"  "<<endl;

		hOrder(p->right);

	}

};

int main()

{

	/***扩展层次序列简立树***/

	//char t[9] = "ABCDE#FG";

	//tree s(t);

	//s.preOrder();

	/***建立二叉排序树***/

	tree s;

	char t[8] = "3289654";

	s.insert(t);

//	s.postOreder();

	cout<<"is Banlance? "<<s.isBanlance(8)<<endl;

	cout<<"Over"<<endl;

	return 0;

}
巴特西

Cracking The Coding Interview 4.1

最新文章

热门文章
