樹

二叉樹

構建二叉樹

?? ?int value;Node left;Node right;public Node(int val) {value=val;}

節點的添加

	Node root=null;public void insert(int num) {Node node=new Node(num);if(root==null) {root=node;return;}Node index = root;while(true) {//插入的節點值小if(index.value>num) {if(index.left==null) {//插入index.left=node;return;}else {index =index.left;}}else {//插入的節點值大if(index.right==null) {index.right=node;return;}else {index=index.right;}}}}

遍歷

		 public void levelQrder() {Queue<Node> queue=new LinkedList<Node>();if(root!=null)queue.add(root);Node index=null;while(!queue.isEmpty()) {index =queue.poll();System.out.print(index.value+"");if(index.left!=null) {queue.add(index.left);}if(index.right!=null) {queue.add(index.right);}}System.out.println();}

查找

查找某個節點

		    public Node search(int num) {Node index=root;while(index!=null&&index.value!=num) {if(index.value>num) {//目標值小index=index.left;}else {index=index.right;}}return index;}

查找某個節點的父節點

		    public Node searchParent(int num) {Node index=root;while (index!=null) {if((index.left!=null&&index.left.value==num)||
(index.right!=null&&index.right.value==num)){return index;}else if(index.value>num) {index=index.left;}else {index = index.right;}}return null;}

查找一棵樹中最小的節點

			public int min(Node treeNode) {Node index = treeNode;while(index.left!=null){index=index.left;}return index.value;}

刪除

? ? 刪除可分為三種情況，即刪除葉子節點、刪除只有一棵子樹的節點、刪除有兩棵子樹的節點

刪除葉子節點

1、找到要刪除的節點target

				if(root==null) {System.out.println("空樹");return;}//找目標節點Node target = search(num);//沒有目標節點if(target==null) {System.out.println("沒有這個節點");return;}

2、找要刪除節點的父節點parent

3、考慮有沒有父節點
? ? ? 如果沒有父節點，那target為根節點root=null

					if(parent==null) {root=null;return;}

4、如果有父節點

? ? ? 討論parenti和target的關系
? ? ? target是父節點的左孩子? ? ? parent.left=null
? ? ? target是父節點的右孩子? ? ? parent.right=null

刪除只有一棵子樹的節點

1、找到要刪除的節點target
2、找要刪除節點的父節點parent
3、考慮有沒有父節點
? ? ? 如果沒有父節點，那target為根節點

? ? ? ?判斷target有左子樹還是右子樹？

? ? ? ?如果目標節點有左子樹? ? root=root.left
? ? ? ?如果目標節點有右子樹? ? root=root.right

4、如果目標節點有父節點

? ? ?判斷目標節點是父節點的左孩子還是右孩子？

（1）目標節點是父節點的左孩子

? ? ? ? ?判斷target有左子樹還是右子樹？

? ? ? ? ?目標節點有左子樹
? ? ? ? ?parent.left =target.left

? ? ? ? ?目標節點有子樹
? ? ? ? ?parent.left =target.left

（2）目標節點是父節點的右孩子

? ? ? ? ?判斷targe有左子還是右子樹？

? ? ? ? ?目標節點有左子樹
? ? ? ? ?parent.right =target.left

? ? ? ? ?目標節點有子樹
? ? ? ? ?parent.left =target.right

刪除有兩棵子樹的節點

1、找目標節點右子樹的最小值（左子樹的最大值）替換掉要刪除的值
2、把目標節點右子樹的最小值（左子樹的最大值）刪除
?

					int minValue = min(target.right);delete(minValue);target.value=minValue;